Numerical Analysis: Beyond Interpolation: The Philosophy of Approximation

Interpolation assumes data is pristine. In the real world, data is messy, jittery, and filled with noise. When we insist on hitting every data point exactly, we don't find the truth—we find chaos. Today, we move beyond the rigid requirements of exactitude into the philosophy of approximation.

The Failure of Exactitude

While a high-degree polynomial can hit every data point, it often results in "Runge-like" oscillations. These wild swings bear no resemblance to the underlying physical process. So it is unreasonable to require that the approximating function agree exactly with the data, especially when measurements are subject to variance.

Defining the 'Best' Fit: The Three Norms

To approximate, we must define an error function $E$. How we measure "closeness" changes the result entirely:

1. The Minimax Problem ($L_{\infty}$)

Seeking to minimize the maximum possible error:

$$E_{\infty}(a_0, a_1) = \max_{1 \le i \le n} \{|y_i - (a_1 x_i + a_0)|\}$$

Pitfall: The minimax approach generally assigns too much weight to a bit of data that is badly in error.

2. Absolute Deviation ($L_1$)

The sum of absolute differences:

$$E_1(a_0, a_1) = \sum_{i=1}^{n} |y_i - (a_1 x_i + a_0)|$$

Pitfall: The absolute-value function is not differentiable at zero, and we might not be able to find solutions to this pair of equations analytically.

3. Least Squares Supremacy ($L_2$)

The standard in numerical analysis, squaring the residuals:

$$E_2(a_0, a_1) = \sum_{i=1}^{n} [y_i - (a_1 x_i + a_0)]^2$$

This creates a smooth, differentiable surface where calculus can easily find a global minimum.

Analytical Constraints

Choosing a metric is a balance of logic and calculus. For example, the absolute deviation method does not give sufficient weight to a point that is considerably out of line with the approximation, while $L_2$ provides a robust middle ground that penalizes large outliers without being entirely governed by a single rogue data point.

🎯 Core Principle

Approximation is the art of ignoring noise to find signal. By shifting from point-matching to error-minimization, we recover the true physical laws obscured by measurement variance.

QUESTION 1

Why is a high-degree interpolating polynomial often a poor choice for experimental data?

It is computationally too simple to represent complex physics.

It results in 'Runge-like' oscillations that capture noise rather than trends.

It always yields a linear result that ignores data curvature.

It is not differentiable at any point.

QUESTION 2

Which error norm is primarily used in the 'Minimax' problem?

L1 Norm (Sum of Absolute Deviations)

L2 Norm (Least Squares)

L∞ Norm (Maximum Absolute Error)

The Gram-Schmidt Norm

QUESTION 3

What is a major computational drawback of the Absolute Deviation (L1) method?

It is too sensitive to small outliers.

It requires the use of Chebyshev polynomials for all calculations.

The absolute-value function is not differentiable at zero.

It only works for datasets with more than 100 points.

QUESTION 4

Which norm strikes a balance by penalizing large outliers significantly but not letting a single error dominate the entire fit?

L1 Norm

L2 Norm (Least Squares)

L∞ Norm

The Runge Norm

QUESTION 5

In the falling object example, why use a least-squares quadratic instead of a high-degree polynomial?

To ensure the object is moving in a straight line.

To capture every vibration of the camera stand.

To ignore camera 'jitter' and recover the physical law of gravity (y = at²).

Because high-speed cameras cannot record more than 3 data points.

Challenge: Advanced Approximation Theory

Mastering Padé and Discrete Least Squares

Approximation theory extends into rational functions and specific data analysis. Test your understanding of these advanced constructs.

Determine all degree 2 Padé approximations for $f(x) = e^{2x}$. Compare results at $x = 0.2, 0.4, 0.6, 0.8, 1.0$.

Model Solution:
The Maclaurin series for $e^{2x}$ is $1 + 2x + 2x^2 + \frac{4}{3}x^3 + \dots$. For degree 2 Padé $R_{n,m}(x) = P_n(x)/Q_m(x)$ where $n+m=2$:

$R_{2,0}$ (Taylor): $1 + 2x + 2x^2$
$R_{1,1}$: $\frac{1+x}{1-x}$
$R_{0,2}$: $\frac{1}{1-2x+2x^2}$

At $x=1$, $e^2 \approx 7.389$. $R_{2,0}(1) = 5$. $R_{1,1}$ is undefined. $R_{0,2}(1) = 1$. This illustrates that low-degree Padé approximations have specific regions of validity.

Given $\phi_0(x) = 2, \phi_1(x) = x - 3$, and $\phi_2(x) = x^2 + 2x + 7$, show that any quadratic $Q(x) = a_0 + a_1x + a_2x^2$ can be expressed as a linear combination $c_0\phi_0 + c_1\phi_1 + c_2\phi_2$.

Model Solution:
This is a basis change problem. We observe the degrees of $\phi_i$: $\text{deg}(\phi_0)=0, \text{deg}(\phi_1)=1, \text{deg}(\phi_2)=2$. Since they are polynomials of distinct degrees, they are linearly independent in $\mathbb{P}_2$.
1. $a_2x^2$ must come from $c_2\phi_2$, so $c_2 = a_2$.
2. The linear term $a_1x$ is then matched by $c_1(x-3) + c_2(2x)$.
3. The constant $a_0$ is matched by $c_0(2) + c_1(-3) + c_2(7)$. Because the leading coefficients form a triangular system, a unique solution for $c_i$ always exists.

Suppose weight $F$ and length $l$ data is: $F=[2, 4, 6]$, $l=[7.0, 9.4, 12.3]$. Find the least squares line $l = mk + b$ (or $F = kl$).

Model Solution:
Let $x = F, y = l$. $\sum x = 12, \sum y = 28.7, \sum x^2 = 56, \sum xy = 127.4$. Normal Equations: $3b + 12m = 28.7$ $12b + 56m = 127.4$ Solving: $m = 1.325$, $b = 4.267$. The least squares approximation for the spring constant (if $F=kl$) would involve a line through the origin, but the data suggests an initial length offset $b$.